/ MacHack 1998 / MacHack 1998.toast / Programming Contest / MacHack Contest.sit / MacHack Contest / Problems Folder / Problem 07 - Graph / Solution.p

< prev

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 0a 53 6f 6c 75 74 69 | 6f 6e 2e 70 00 00 00 00 |..Soluti|on.p....|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 43 57 49 | 45 00 00 00 00 00 00 00 |.TEXTCWI|E.......|
|00000050| 00 00 00 00 00 07 d3 00 | 00 01 9a b1 ae f5 70 b1 |........|......p.|
|00000060| ae f5 70 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |..p.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 1e a6 00 00 |........|........|
|00000080| 28 2a 0d 50 72 6f 62 6c | 65 6d 20 30 37 20 2d 20 |(*.Probl|em 07 - |
|00000090| 47 72 61 70 68 0d 0d 70 | 72 6f 63 65 64 75 72 65 |Graph..p|rocedure|
|000000a0| 20 47 72 61 70 68 49 6e | 69 74 28 20 76 61 72 20 | GraphIn|it( var |
|000000b0| 67 72 61 70 68 3a 20 48 | 61 6e 64 6c 65 3b 20 76 |graph: H|andle; v|
|000000c0| 65 72 72 74 69 63 69 65 | 73 3a 20 55 49 6e 74 33 |errticie|s: UInt3|
|000000d0| 32 20 29 3b 0d 70 72 6f | 63 65 64 75 72 65 20 47 |2 );.pro|cedure G|
|000000e0| 72 61 70 68 41 64 64 44 | 69 72 65 63 74 65 64 45 |raphAddD|irectedE|
|000000f0| 64 67 65 28 20 67 72 61 | 70 68 3a 20 48 61 6e 64 |dge( gra|ph: Hand|
|00000100| 6c 65 3b 20 76 65 72 74 | 65 78 31 2c 20 76 65 72 |le; vert|ex1, ver|
|00000110| 74 65 78 32 3a 20 55 49 | 6e 74 33 32 20 29 3b 0d |tex2: UI|nt32 );.|
|00000120| 70 72 6f 63 65 64 75 72 | 65 20 47 72 61 70 68 46 |procedur|e GraphF|
|00000130| 69 6e 64 52 6f 75 74 65 | 28 20 67 72 61 70 68 3a |indRoute|( graph:|
|00000140| 20 48 61 6e 64 6c 65 3b | 20 76 65 72 74 65 78 31 | Handle;| vertex1|
|00000150| 2c 20 76 65 72 74 65 78 | 32 3a 20 55 49 6e 74 33 |, vertex|2: UInt3|
|00000160| 32 3b 20 76 61 72 0d 76 | 65 72 74 69 63 69 65 73 |2; var.v|erticies|
|00000170| 3a 20 48 61 6e 64 6c 65 | 20 29 3b 0d 0d 59 6f 75 |: Handle| );..You|
|00000180| 72 20 74 61 73 6b 20 69 | 73 20 74 6f 20 77 72 69 |r task i|s to wri|
|00000190| 74 65 20 61 20 73 65 74 | 20 6f 66 20 72 6f 75 74 |te a set| of rout|
|000001a0| 69 6e 65 73 20 74 6f 20 | 63 72 65 61 74 65 20 61 |ines to |create a|
|000001b0| 6e 64 20 74 72 61 76 65 | 72 73 65 20 61 20 64 69 |nd trave|rse a di|
|000001c0| 72 65 63 74 65 64 0d 67 | 72 61 70 68 2e 0d 0d 47 |rected.g|raph...G|
|000001d0| 72 61 70 68 49 6e 69 74 | 20 63 72 65 61 74 65 73 |raphInit| creates|
|000001e0| 20 61 20 6e 65 77 2c 20 | 65 6d 70 74 79 20 64 69 | a new, |empty di|
|000001f0| 72 65 63 74 65 64 20 67 | 72 61 70 68 20 72 65 61 |rected g|raph rea|
|00000200| 64 79 20 74 6f 20 61 63 | 63 65 70 74 20 64 69 72 |dy to ac|cept dir|
|00000210| 65 63 74 65 64 20 65 64 | 67 65 73 0d 77 69 74 68 |ected ed|ges.with|
|00000220| 20 76 65 72 72 74 69 63 | 69 65 73 20 76 65 72 74 | verrtic|ies vert|
|00000230| 69 63 69 65 73 2e 20 20 | 0d 0d 47 72 61 70 68 41 |icies.  |..GraphA|
|00000240| 64 64 44 69 72 65 63 74 | 65 64 45 64 67 65 20 61 |ddDirect|edEdge a|
|00000250| 64 64 73 20 61 20 64 69 | 72 65 63 74 65 64 20 65 |dds a di|rected e|
|00000260| 64 67 65 20 66 72 6f 6d | 20 76 65 72 74 65 78 31 |dge from| vertex1|
|00000270| 20 74 6f 20 76 65 72 74 | 65 78 32 0d 0d 47 72 61 | to vert|ex2..Gra|
|00000280| 70 68 46 69 6e 64 52 6f | 75 74 65 20 66 69 6e 64 |phFindRo|ute find|
|00000290| 20 61 20 72 6f 75 74 65 | 20 66 72 6f 6d 20 76 65 | a route| from ve|
|000002a0| 72 74 65 78 31 20 74 6f | 20 76 65 72 74 65 78 32 |rtex1 to| vertex2|
|000002b0| 2e 20 20 49 66 20 73 75 | 63 68 20 61 20 72 6f 75 |.  If su|ch a rou|
|000002c0| 74 65 20 65 78 69 73 74 | 73 2c 0d 74 68 65 6e 20 |te exist|s,.then |
|000002d0| 76 65 72 74 69 63 69 65 | 73 20 69 73 20 72 65 74 |verticie|s is ret|
|000002e0| 75 72 6e 73 20 61 73 20 | 61 20 72 65 61 6c 20 4d |urns as |a real M|
|000002f0| 61 63 20 68 61 6e 64 6c | 65 20 74 6f 20 61 6e 20 |ac handl|e to an |
|00000300| 61 72 72 61 79 20 6f 66 | 20 55 49 6e 74 33 32 73 |array of| UInt32s|
|00000310| 2c 20 74 68 65 0d 66 69 | 72 73 74 20 69 73 20 76 |, the.fi|rst is v|
|00000320| 65 72 74 65 78 31 2c 20 | 74 68 65 20 6c 61 73 74 |ertex1, |the last|
|00000330| 20 69 73 20 76 65 72 74 | 65 78 32 2e 20 20 45 61 | is vert|ex2.  Ea|
|00000340| 63 68 20 73 75 63 63 65 | 73 73 69 76 65 20 76 65 |ch succe|ssive ve|
|00000350| 72 74 65 78 20 6d 75 73 | 74 20 68 61 76 65 0d 70 |rtex mus|t have.p|
|00000360| 72 65 76 69 6f 75 73 6c | 79 20 68 61 64 20 61 6e |reviousl|y had an|
|00000370| 20 65 64 67 65 20 61 64 | 64 65 64 20 77 69 74 68 | edge ad|ded with|
|00000380| 20 47 72 61 70 68 41 64 | 64 44 69 72 65 63 74 65 | GraphAd|dDirecte|
|00000390| 64 45 64 67 65 2e 20 20 | 49 66 20 6e 6f 20 72 6f |dEdge.  |If no ro|
|000003a0| 75 74 65 20 65 78 69 73 | 74 73 2c 0d 72 65 74 75 |ute exis|ts,.retu|
|000003b0| 72 6e 20 6e 69 6c 20 66 | 6f 72 20 76 65 72 74 69 |rn nil f|or verti|
|000003c0| 63 69 65 73 2e 20 20 4e | 6f 20 76 65 72 74 65 78 |cies.  N|o vertex|
|000003d0| 20 73 68 6f 75 6c 64 20 | 61 70 70 65 61 72 20 6d | should |appear m|
|000003e0| 6f 72 65 20 74 68 61 6e | 20 6f 6e 63 65 20 69 6e |ore than| once in|
|000003f0| 20 74 68 65 0d 76 65 72 | 74 69 63 69 65 73 20 68 | the.ver|ticies h|
|00000400| 61 6e 64 6c 65 2c 20 65 | 78 63 65 70 74 20 66 6f |andle, e|xcept fo|
|00000410| 72 20 74 68 65 20 63 61 | 73 65 20 77 68 65 72 65 |r the ca|se where|
|00000420| 20 76 65 72 74 65 78 31 | 20 69 73 20 74 68 65 20 | vertex1| is the |
|00000430| 73 61 6d 65 20 61 73 20 | 76 65 72 74 65 78 32 2c |same as |vertex2,|
|00000440| 20 69 6e 0d 77 68 69 63 | 68 20 63 61 73 65 20 79 | in.whic|h case y|
|00000450| 6f 75 20 6d 75 73 74 20 | 66 69 6e 64 20 61 20 63 |ou must |find a c|
|00000460| 69 72 63 75 6c 61 72 20 | 72 6f 75 74 65 20 66 72 |ircular |route fr|
|00000470| 6f 6d 20 76 65 72 74 65 | 78 31 20 62 61 63 6b 20 |om verte|x1 back |
|00000480| 74 6f 20 69 74 73 65 6c | 66 20 61 6e 64 20 73 6f |to itsel|f and so|
|00000490| 0d 76 65 72 74 65 78 31 | 20 77 69 6c 6c 20 61 70 |.vertex1| will ap|
|000004a0| 70 65 61 72 20 65 78 61 | 63 74 6c 79 20 74 77 69 |pear exa|ctly twi|
|000004b0| 63 65 2c 20 6f 6e 63 65 | 20 61 74 20 74 68 65 20 |ce, once| at the |
|000004c0| 73 74 61 72 74 20 61 6e | 64 20 6f 6e 63 65 20 61 |start an|d once a|
|000004d0| 74 20 74 68 65 20 65 6e | 64 20 6f 66 20 74 68 65 |t the en|d of the|
|000004e0| 0d 76 65 72 74 69 63 69 | 65 73 20 68 61 6e 64 6c |.vertici|es handl|
|000004f0| 65 2e 0d 0d 41 6c 6c 20 | 74 68 65 20 67 72 61 70 |e...All |the grap|
|00000500| 68 20 69 6e 66 6f 72 6d | 61 74 69 6f 6e 20 6d 75 |h inform|ation mu|
|00000510| 73 74 20 62 65 20 73 74 | 6f 72 65 64 20 69 6e 20 |st be st|ored in |
|00000520| 74 68 65 20 72 65 61 6c | 20 4d 61 63 20 6d 65 6d |the real| Mac mem|
|00000530| 6f 72 79 20 6d 61 6e 61 | 67 65 72 20 68 61 6e 64 |ory mana|ger hand|
|00000540| 6c 65 0d 2d 20 69 74 20 | 77 69 6c 6c 20 62 65 20 |le.- it |will be |
|00000550| 64 69 73 70 6f 73 65 64 | 20 77 69 74 68 20 44 69 |disposed| with Di|
|00000560| 73 70 6f 73 65 48 61 6e | 64 6c 65 20 61 6e 64 20 |sposeHan|dle and |
|00000570| 74 68 61 74 20 6d 75 73 | 74 20 72 65 6c 65 61 73 |that mus|t releas|
|00000580| 65 20 61 6c 6c 20 6d 65 | 6d 6f 72 79 2c 20 73 6f |e all me|mory, so|
|00000590| 0d 64 6f 6e 74 20 73 74 | 6f 72 65 20 61 6e 79 20 |.dont st|ore any |
|000005a0| 65 78 74 72 61 20 69 6e | 66 6f 72 6d 61 74 69 6f |extra in|formatio|
|000005b0| 6e 20 6f 75 74 73 69 64 | 65 20 74 68 65 20 68 61 |n outsid|e the ha|
|000005c0| 6e 64 6c 65 2e 20 20 41 | 6c 73 6f 2c 20 79 6f 75 |ndle.  A|lso, you|
|000005d0| 20 6d 75 73 74 20 62 65 | 20 61 62 6c 65 20 74 6f | must be| able to|
|000005e0| 0d 64 65 61 6c 20 77 69 | 74 68 20 68 61 76 69 6e |.deal wi|th havin|
|000005f0| 67 20 6d 75 6c 74 69 70 | 6c 65 20 67 72 61 70 68 |g multip|le graph|
|00000600| 73 20 69 6e 73 74 61 6e | 74 69 61 74 65 64 20 73 |s instan|tiated s|
|00000610| 69 6d 75 6c 74 61 6e 65 | 6f 75 73 6c 79 2e 0d 2a |imultane|ously..*|
|00000620| 29 0d 0d 75 6e 69 74 20 | 53 6f 6c 75 74 69 6f 6e |)..unit |Solution|
|00000630| 3b 0d 0d 69 6e 74 65 72 | 66 61 63 65 0d 0d 2f 2f |;..inter|face..//|
|00000640| 20 44 6f 20 6e 6f 74 20 | 6d 6f 64 69 66 79 20 74 | Do not |modify t|
|00000650| 68 65 20 69 6e 74 65 72 | 66 61 63 65 0d 0d 09 75 |he inter|face...u|
|00000660| 73 65 73 0d 09 09 54 79 | 70 65 73 2c 20 46 69 6c |ses...Ty|pes, Fil|
|00000670| 65 73 3b 0d 09 09 0d 09 | 74 79 70 65 0d 09 09 55 |es;.....|type...U|
|00000680| 49 6e 74 33 32 41 72 72 | 61 79 20 3d 20 61 72 72 |Int32Arr|ay = arr|
|00000690| 61 79 5b 30 2e 2e 30 5d | 20 6f 66 20 55 49 6e 74 |ay[0..0]| of UInt|
|000006a0| 33 32 3b 0d 09 09 55 49 | 6e 74 33 32 41 72 72 61 |32;...UI|nt32Arra|
|000006b0| 79 50 74 72 20 3d 20 5e | 55 49 6e 74 33 32 41 72 |yPtr = ^|UInt32Ar|
|000006c0| 72 61 79 3b 0d 09 09 55 | 49 6e 74 33 32 41 72 72 |ray;...U|Int32Arr|
|000006d0| 61 79 48 61 6e 64 6c 65 | 20 3d 20 5e 55 49 6e 74 |ayHandle| = ^UInt|
|000006e0| 33 32 41 72 72 61 79 50 | 74 72 3b 0d 0d 09 70 72 |32ArrayP|tr;...pr|
|000006f0| 6f 63 65 64 75 72 65 20 | 47 72 61 70 68 49 6e 69 |ocedure |GraphIni|
|00000700| 74 28 20 76 61 72 20 67 | 72 61 70 68 3a 20 48 61 |t( var g|raph: Ha|
|00000710| 6e 64 6c 65 3b 20 76 65 | 72 74 69 63 69 65 73 3a |ndle; ve|rticies:|
|00000720| 20 55 49 6e 74 33 32 20 | 29 3b 0d 09 70 72 6f 63 | UInt32 |);..proc|
|00000730| 65 64 75 72 65 20 47 72 | 61 70 68 41 64 64 44 69 |edure Gr|aphAddDi|
|00000740| 72 65 63 74 65 64 45 64 | 67 65 28 20 67 72 61 70 |rectedEd|ge( grap|
|00000750| 68 3a 20 48 61 6e 64 6c | 65 3b 20 76 65 72 74 65 |h: Handl|e; verte|
|00000760| 78 31 2c 20 76 65 72 74 | 65 78 32 3a 20 55 49 6e |x1, vert|ex2: UIn|
|00000770| 74 33 32 20 29 3b 0d 09 | 70 72 6f 63 65 64 75 72 |t32 );..|procedur|
|00000780| 65 20 47 72 61 70 68 46 | 69 6e 64 52 6f 75 74 65 |e GraphF|indRoute|
|00000790| 28 20 67 72 61 70 68 3a | 20 48 61 6e 64 6c 65 3b |( graph:| Handle;|
|000007a0| 20 76 65 72 74 65 78 31 | 2c 20 76 65 72 74 65 78 | vertex1|, vertex|
|000007b0| 32 3a 20 55 49 6e 74 33 | 32 3b 20 76 61 72 20 76 |2: UInt3|2; var v|
|000007c0| 65 72 74 69 63 69 65 73 | 3a 20 55 49 6e 74 33 32 |erticies|: UInt32|
|000007d0| 41 72 72 61 79 48 61 6e | 64 6c 65 20 29 3b 0d 0d |ArrayHan|dle );..|
|000007e0| 0d 69 6d 70 6c 65 6d 65 | 6e 74 61 74 69 6f 6e 0d |.impleme|ntation.|
|000007f0| 0d 2f 2f 20 46 69 6c 6c | 20 69 6e 20 79 6f 75 72 |.// Fill| in your|
|00000800| 20 73 6f 6c 75 74 69 6f | 6e 20 61 6e 64 20 74 68 | solutio|n and th|
|00000810| 65 6e 20 73 75 62 6d 69 | 74 20 74 68 69 73 20 66 |en submi|t this f|
|00000820| 6f 6c 64 65 72 0d 0d 2f | 2f 20 54 65 61 6d 20 4e |older../|/ Team N|
|00000830| 61 6d 65 3a 20 46 49 4c | 4c 20 49 4e 20 59 4f 55 |ame: FIL|L IN YOU|
|00000840| 52 20 54 45 41 4d 20 4e | 41 4d 45 21 0d 0d 65 6e |R TEAM N|AME!..en|
|00000850| 64 2e 0d 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |d.......|........|
|00000860| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000870| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000880| 00 00 01 00 00 00 01 54 | 00 00 00 54 00 00 00 46 |.......T|...T...F|
|00000890| 2b 30 38 30 30 31 35 3a | 35 35 3a 33 32 20 31 39 |+080015:|55:32 19|
|000008a0| 39 38 00 00 00 00 00 00 | 00 00 b1 78 6a 77 00 00 |98......|...xjw..|
|000008b0| 0a 53 6f 6c 75 74 69 6f | 6e 2e 70 73 6d 6d 75 6e |.Solutio|n.psmmun|
|000008c0| 69 63 61 74 6f 72 aa 20 | 34 2e 30 34 32 65 73 69 |icator. |4.042esi|
|000008d0| 02 4a 50 61 72 74 53 49 | 54 21 00 00 00 00 00 00 |.JPartSI|T!......|
|000008e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000008f0| 00 00 b1 b0 40 8e 00 00 | 00 00 00 00 01 9a 00 00 |....@...|........|
|00000900| 00 00 29 bc 7f 92 00 00 | 00 00 20 52 65 3a 20 46 |..).....|.. Re: F|
|00000910| 6f 6c 64 65 72 20 48 69 | 65 72 61 72 63 68 79 20 |older Hi|erarchy |
|00000920| 44 75 70 6c 69 63 61 74 | 69 6f 6e 0d 00 00 00 00 |Duplicat|ion.....|
|00000930| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000940| 00 00 00 00 00 00 00 00 | 00 04 36 35 37 a4 00 00 |........|..657...|
|00000950| 00 00 00 00 00 00 00 00 | 00 01 be ab 00 00 05 f2 |........|........|
|00000960| 00 00 02 90 02 07 31 32 | 2f 35 2f 39 38 34 30 30 |......12|/5/98400|
|00000970| 30 32 31 3a 30 31 3a 35 | 36 20 31 39 39 38 00 00 |021:01:5|6 1998..|
|00000980| 00 00 00 48 00 0a 47 65 | 6e 65 76 61 00 00 00 00 |...H..Ge|neva....|
|00000990| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009a0| 00 00 00 00 00 00 00 02 | 00 02 00 2c 00 08 01 f1 |........|...,....|
|000009b0| 01 fa 00 2c 00 08 01 f1 | 01 fa b1 ae ad 75 00 00 |...,....|.....u..|
|000009c0| 07 d3 00 00 07 d3 00 00 | 05 61 01 00 00 00 00 04 |........|.a......|
|000009d0| 00 01 00 01 00 00 01 00 | 00 00 01 54 00 00 00 54 |........|...T...T|
|000009e0| 00 00 00 46 00 ce 0d f8 | 26 90 00 00 00 1c 00 46 |...F....|&......F|
|000009f0| 00 01 4d 50 53 52 00 00 | 00 12 4d 57 42 42 00 00 |..MPSR..|..MWBB..|
|00000a00| 00 1e 03 ed ff ff 00 00 | 00 00 00 00 00 00 03 f0 |........|........|
|00000a10| ff ff 00 00 00 4c 00 00 | 00 00 00 00 00 00 00 00 |.....L..|........|
|00000a20| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000a30| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000a40| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000a50| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000a60| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000a70| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
+--------+-------------------------+-------------------------+--------+--------+